1. Technical Field
The present invention relates to branch predictions in general, and, in particular, to a method and apparatus for performing branch predictions. Still more particularly, the present invention relates to a method and apparatus for updating global branch history information.
2. Description of Related Art
Within a data processing system, instructions are typically stored in consecutive memory locations within a system memory. During operation, instructions are fetched from consecutive memory locations by a processor. Each time an instruction is fetched from the system memory, a program counter within the processor is incremented so that the program counter contains the memory address of a subsequent instruction. The instructions fetching, program counter incrementing, and instructions execution continues linearly through the system memory until a program control instruction is encountered. A program control instruction, when executed, changes the memory address in the program counter and causes the flow of the program execution to be altered. Examples of program control instructions include Branch, Jump conditionally, Call, and Return.
For a processor that includes a pipeline architecture, it is often not clear whether or not a branch instruction will alter the program flow until the branch instruction reaches a late stage in the pipeline. But the processor may have already fetched other instructions and is executing them in early stages of the pipeline. If the branch instruction causes a change in the program flow, all of the instructions within the pipeline that followed the branch instruction must be thrown out, which typically results in processing delays.
To alleviate such processing delays, many pipelined processors use branch prediction mechanisms to predict the outcome of branch instructions, and then fetch subsequent instructions according to the branch prediction. Branch prediction mechanisms can be either static or dynamic.
With a static branch prediction mechanism, the prediction remains the same for a given branch instruction throughout the entire execution of the program in which the branch instruction is contained. In contrast, a dynamic branch prediction mechanism keeps a history of the outcome of branch instructions as a program executes and makes branch predictions based upon such history.
The simplest dynamic branch prediction mechanism is an array of one-bit storage elements, commonly referred to as a branch history table (BHT). A portion of the address of a branch instruction is typically used to index into the BHT. Each entry within the BHT may contain a two-bit counter. Since a two-bit counter can provide a decimal range of 0 to 3, high values (such as 2 or 3) can be used to represent taken branches, and low values (such as 0 or 1) can be used to represent not-taken branches. If the value in the two-bit counter is a 2 or 3, a branch is predicted to be taken. On the other hand, if the value in the two-bit counter is a 0 or 1, a branch is predicted to be not-taken. The actual outcome of a branch instruction is known once a branch instruction has been executed. If the branch was taken, the two-bit counter is incremented, saturating at 3. If the branch was not-taken, the two-bit counter is decremented, saturating at 0. Each time a branch instruction is executed, the BHT is updated based on the outcome of the execution. The history in a BHT is commonly referred to as a local branch history since it records branch history on an individual branch instruction basis.
It has been observed that the behavior of a given branch instruction in a program is often correlated with the behavior of other branch instructions in the program. Therefore, when making a branch prediction about a particular branch instruction, some branch predictors use the history of that particular branch instruction along with the behavior of other branch instructions. The history of all branch instructions is commonly referred to as a global branch history (GBH).
Generally speaking, conventional methods of updating GBH information suffer from two problems. The first problem is attributed to the delays in updating GBH information to reflect new branch instructions. If the GBH can be read, the branch prediction(s) can be made, and the GBH can be updated all in one cycle, then the above-mentioned problem would not exist. However, current processors typically have a multi-cycle branch prediction mechanism, as required by high clock frequencies. Thus, it is typically not possible to perform a single cycle branch prediction, and a method is needed to quickly update the GBH information for the next prediction before the previous prediction is completed.
The second problem with conventional methods of updating GBH information is the requirement for branch instructions to keep track of GBH information. Basically, a branch instruction must record GBH bits that are used to index into a branch prediction table. Many forms of branch prediction require updating some state using the GBH after the branch has been resolved, even in the absence of a flush. The same value of the GBH as read when making the branch prediction typically needs to be used when updating the state. If it is possible for the GBH bits to be out-of-date when read, unless it is possible to recreate exactly how the GBH bits are out of date, then the only way to know what the value of the GBH bits read in the beginning of the pipeline is for the branch instruction to record such information. Recording such information requires additional overhead.
Consequently, it would be desirable to provide an improved method and apparatus for updating GBH information.